# 52/100 图论-腐烂的橘子
# leetcode第994题: https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/13
from collections import deque

from leetcode import test


def orangesRotting_bfs(grid: list[list[int]]) -> int:
    """我的方法, 利用多次广度优先遍历"""
    m, n = len(grid), len(grid[0])
    rotted = set()
    changed = True
    res = 0
    while changed:
        changed = False
        queue = deque([(0, 0)])
        visited = [[False] * n for _ in range(m)]
        while queue:
            cur = queue.popleft()
            flag = False
            if not visited[cur[0]][cur[1]]:  # 如果该节点没有遍历
                visited[cur[0]][cur[1]] = True
                if grid[cur[0]][cur[1]] == 2:  # 如果当前的果子是腐烂的
                    rotted.add((cur[0], cur[1]))  # 将腐烂的果子的坐标添加到rotted集合中
                    flag = True
                if cur[0] - 1 >= 0:  # 上
                    if flag and grid[cur[0] - 1][cur[1]] == 1:  # 如果当前是腐烂果子, 则将它的邻居添加到rotted集合
                        rotted.add((cur[0] - 1, cur[1]))
                        changed = True
                if cur[0] + 1 < m:  # 下
                    if flag and grid[cur[0] + 1][cur[1]] == 1:
                        rotted.add((cur[0] + 1, cur[1]))
                        changed = True
                    queue.append((cur[0] + 1, cur[1]))  # 添加到遍历队列
                if cur[1] - 1 >= 0:  # 左
                    if flag and grid[cur[0]][cur[1] - 1] == 1:
                        rotted.add((cur[0], cur[1] - 1))
                        changed = True
                if cur[1] + 1 < n:  # 右
                    if flag and grid[cur[0]][cur[1] + 1] == 1:
                        rotted.add((cur[0], cur[1] + 1))
                        changed = True
                    queue.append((cur[0], cur[1] + 1))  # 添加到遍历队列
        for x, y in rotted:  # 修改果子的状态
            grid[x][y] = 2
        if changed:
            res += 1

    if any(1 in row for row in grid):
        return -1
    return res


def orangesRotting_official(grid: list[list[int]]) -> int:
    """不同于我的方法, 官方方法只标记已经腐烂的果子, 并将已经腐烂的果子加入队列, 每次只更新腐烂果子四个方向的空格"""
    R, C = len(grid), len(grid[0])

    # queue - all starting cells with rotting oranges
    queue = deque()
    for r, row in enumerate(grid):
        for c, val in enumerate(row):
            if val == 2:
                queue.append((r, c, 0))

    def neighbors(r, c) -> (int, int):
        for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
            if 0 <= nr < R and 0 <= nc < C:
                yield nr, nc

    d = 0
    while queue:
        r, c, d = queue.popleft()
        for nr, nc in neighbors(r, c):
            if grid[nr][nc] == 1:
                grid[nr][nc] = 2
                queue.append((nr, nc, d + 1))

    if any(1 in row for row in grid):
        return -1
    return d


if __name__ == '__main__':
    grid = [[2, 1, 1],
            [1, 1, 0],
            [0, 1, 1]]
    grid1 = [[2, 1, 1],
             [0, 1, 1],
             [1, 0, 1]]
    grid2 = [[0, 2]]

    inp = [{"grid": grid}, {"grid": grid1}, {"grid": grid2}, ]
    out = [4, -1, 0]

    test.test_function(orangesRotting_bfs, inp, out, times=1000)
    test.test_function(orangesRotting_official, inp, out, times=1000)
